package day0401;

import java.util.Arrays;
import java.util.Scanner;

public class Jump36 {
    /**
     * 36:小明和朋友玩跳格子游戏 DFS
     * 小明和朋友玩跳格子游戏， 有 n 个连续格子，每个格子有不同的分数，小朋友可以选择
     * 从任意格子起跳，但是不能跳连续的格子，也不能回头跳;
     * 给定一个代表每个格子得分的非负整数数组，计算能够得到的最高分数。
     * 输入描述：
     * 给定一个数例，如：
     * 1 2 3 1
     * 输出描述：
     * 输出能够得到的最高分，如：
     * 4
     * 补充说明：
     * 1 <= nums.length <= 100
     * 0 <= nums[i] <= 1000
     * 示例 1
     * 输入：
     * 1 2 3 1
     * 输出：
     * 4
     * 说明：
     * 选择跳第一个格子和第三个格子
     * 示例 2
     * 输入：
     * 2 7 9 3 1
     * 1 1 8 9 3
     * 输出：
     * 12
     * 说明：
     * 2+9+1=12
     */
    /*
     * 跳格子：隔一个或隔两格，只有这两种情况
     * */
    private static int max = Integer.MIN_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] arr = Arrays.stream(sc.nextLine().split(" ")).map(Integer::parseInt).mapToInt(Integer::intValue).toArray();
        int[] direction = {2, 3};
        int sum = arr[0];
        int res = dfs(arr, direction, 0, sum);
        System.out.println(res);

    }

    private static int dfs(int[] arr, int[] direction, int x, int sum) {
        if (x >= arr.length - 1) {
            max = Math.max(max, sum);
            return max;
        }
        for (int i = 0; i < direction.length; i++) {
            int newX = x + direction[i];
            if (newX <= arr.length - 1) {
                sum += arr[newX];
            }
            dfs(arr, direction, newX, sum);
            x = newX - direction[i];
            sum = 0;
        }
        return max;
    }
}

